Gazociągi
Limit pamięci: 32 MB
Koncern GazBit zamierza zdominować rynek gazowy w Bajtocji.
Specjaliści umiejscowili już na mapie Bajtocji optymalne położenia
punktów wydobycia gazu oraz stacji dystrybucji gazu - pozostało jeszcze
tylko przyporządkować stacje do punktów wydobycia.
Każda stacja dystrybucji ma być połączona z dokładnie jednym punktem
wydobycia i odwrotnie, każdy punkt wydobycia z dokładnie jedną stacją.
GazBit specjalizuje się w budowie gazociągów prowadzących
z punktów wydobycia do stacji dystrybucji
w kierunku południowym i wschodnim - dokładniej,
każdy wybudowany gazociąg ma (patrząc z lotu ptaka) kształt
łamanej, której każda kolejna część biegnie w kierunku południowym
lub wschodnim i jest prostopadła do poprzedniej.
Zarząd koncernu zastanawia się, jak przyporządkować punktom wydobycia gazu
stacje dystrybucji tak, by zminimalizować łączną długość koniecznych do
wybudowania gazociągów.
Przy planowaniu można pominąć problem przecinania się gazociągów
- ich kolidujące fragmenty zostaną umieszczone na
różnych głębokościach pod ziemią.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia planowane położenia punktów wydobycia
i stacji dystrybucji gazu,
-
wyznaczy takie przyporządkowanie stacji
dystrybucji do punktów wydobycia, które pozwala na wybudowanie
gazociągów o minimalnej łącznej długości,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę punktów wydobycia
(równą liczbie stacji dystrybucji).
Kolejne wierszy zawiera po dwie liczby całkowite i
( dla ),
oddzielone pojedynczym
odstępem i oznaczające współrzędne na mapie punktów wydobycia gazu.
Przyjmujemy, że wraz z rosnącą współrzędną poruszamy się na wschód,
a wraz z rosnącą współrzędną poruszamy się na północ.
Następne wierszy zawiera po dwie liczby całkowite i
( dla ), oddzielone
pojedynczym odstępem i oznaczające współrzędne na mapie stacji
dystrybucji gazu.
Zarówno punkty wydobycia, jak i stacje dystrybucji numerujemy liczbami
naturalnymi od 1 do w kolejności występowania na wejściu.
Żadna para współrzędnych nie powtórzy się w jednym zestawie danych
wejściowych.
Ponadto dla każdych danych wejściowych istnieje jakieś przyporządkowanie
punktom wydobycia stacji dystrybucji, które można zrealizować
za pomocą gazociągów idących tylko na południe i wschód.
Wyjście
Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą,
oznaczającą minimalną sumaryczną długość wszystkich koniecznych
do wybudowania gazociągów.
Dalej na wyjściu powinien wystąpić przykładowy opis przyporządkowania
stacji punktom wydobycia, który realizuje to minimum.
Każdy z kolejnych wierszy powinien zawierać dwie liczby całkowite,
oddzielone pojedynczym odstępem i oznaczające numery punktu wydobycia
i stacji dystrybucji, które powinny być połączone gazociągiem.
Kolejność wypisywania przyporządkowań może być dowolna.
Jeżeli istnieje wiele poprawnych rozwiązań, Twój program powinien
wypisać jakiekolwiek z nich.
Przykład
Dla danych wejściowych:
3
3 5
1 2
4 3
6 3
5 2
2 1
poprawną odpowiedzią jest:
9
2 3
1 2
3 1
Autor zadania: Jakub Radoszewski.